package code201_300.code80_90;

/**
 * 给定一个包含 [0, n] 中 n 个数的数组 nums ，找出 [0, n] 这个范围内没有出现在数组中的那个数。
 *
 * 输入：nums = [3,0,1]
 * 输出：2
 * 解释：n = 3，因为有 3 个数字，所以所有的数字都在范围 [0,3] 内。2 是丢失的数字，因为它没有出现在 nums 中。
 *
 * 输入：nums = [0,1]
 * 输出：2
 * 解释：n = 2，因为有 2 个数字，所以所有的数字都在范围 [0,2] 内。2 是丢失的数字，因为它没有出现在 nums 中。
 *
 * 输入：nums = [9,6,4,2,3,5,7,0,1]
 * 输出：8
 * 解释：n = 9，因为有 9 个数字，所以所有的数字都在范围 [0,9] 内。8 是丢失的数字，因为它没有出现在 nums 中。
 *
 * 输入：nums = [0]
 * 输出：1
 * 解释：n = 1，因为有 1 个数字，所以所有的数字都在范围 [0,1] 内。1 是丢失的数字，因为它没有出现在 nums 中。
 *
 * 进阶：你能否实现线性时间复杂度、仅使用额外常数空间的算法解决此问题?
 *
 */
public class _286missingNumber {

    /**
     * 直接考虑进阶算法：实现线性时间复杂度和常数空间算法。
     * 执行用时：     * 0 ms     * , 在所有 Java 提交中击败了     * 100.00%     * 的用户
     * 内存消耗：     * 38.4 MB     * , 在所有 Java 提交中击败了     * 91.42%     * 的用户
     * @param nums
     * @return
     */
    public int missingNumber(int[] nums) {
        int max = 0;
        int sumMax = 0;
        int sum = 0;
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
            if(max<nums[i])max = nums[i];
        }
        for (int i = 1; i <= max; i++) {
            sumMax += i;
        }
        if(sumMax==sum&&nums.length==max+1)return max+1;
        return sumMax-sum;
    }

}
